﻿/*
 * @autor: hectorea
 * @date: 02/08/12
 * @project: SquareRoot
 * @Reference:
 *  http://en.wikipedia.org/wiki/Binary_tree
 *  http://en.wikipedia.org/wiki/Depth-first_search
 *  http://en.wikipedia.org/wiki/Breadth-first_search
 *  http://classes.soe.ucsc.edu/cmps012b/Spring97/Lecture16/sld008.htm
 *  http://tekpool.wordpress.com/2006/11/04/binary-tree-traversal-breadth-first-aka-width-first-aka-level-order/
 *  http://msdn.microsoft.com/en-US/library/ms379572(v=vs.80)#datastructures20_3_topic3
 *  http://stackoverflow.com/questions/1484473/how-can-i-find-the-common-ancestor-of-two-nodes-in-a-binary-tree
 *  http://www.leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-ii.html
 *  
 */

using System;
using System.Collections.Generic;

namespace BinaryTrees
{
    /// <summary>
    /// A binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". 
    /// </summary>
    public  class BinaryTree
    {
        private BinaryTreeNode _root;       

        public BinaryTreeNode Root
        {
            get { return _root; }
            set { _root = value; }
        }

        public BinaryTree()
        {
            this._root = null;
        }

        #region [ Internal Methods ]
        /// <summary>
        /// Clear the BinaryTree
        /// </summary>
        internal void Clear()
        {
            this._root = null;
        }
        /// <summary>
        /// In-Order: Left child, Root, Right child
        /// </summary>
        /// <param name="btNode">The BinaryTree to be traversed</param>
        internal void InOrder(BinaryTreeNode btNode)
        {
            if (btNode != null)
            {
                InOrder(btNode.Left);
                btNode.DisplayNode();
                InOrder(btNode.Right);
            }
        }
        /// <summary>
        /// Pre-Order: Root, Left child, Right child
        /// </summary>
        /// <param name="btNode">The BinaryTree to be traversed</param>
        internal void PreOrder(BinaryTreeNode btNode)
        {
            if (btNode != null)
            {
                btNode.DisplayNode();
                PreOrder(btNode.Left);
                PreOrder(btNode.Right);
            }

        }
        /// <summary>
        /// Post-Order: Left Child, Right child, Root
        /// </summary>
        /// <param name="btNode">The BinaryTree to be traversed</param>
        internal void PostOrder(BinaryTreeNode btNode)
        {
            if (btNode != null)
            {
                PostOrder(btNode.Left);
                PostOrder(btNode.Right);
                btNode.DisplayNode();
            }
        }
        /// <summary>
        /// The BFS begins at a root node and inspect all the neighboring nodes. Then for each of those neighbor nodes in turn, 
        /// it inspects their neighbor nodes which were unvisited, and so on
        /// </summary>
        /// <param name="btNode">The BinaryTree to be traversed</param>
        internal void BreadthFirst(BinaryTreeNode btNode)
        {
            Queue<BinaryTreeNode> queue = new Queue<BinaryTreeNode>();
            queue.Enqueue(btNode);

            while (queue.Count > 0)
            {
                BinaryTreeNode current = queue.Dequeue();
                current.DisplayNode();

                if (current.Left != null)
                    queue.Enqueue(current.Left);
                if (current.Right != null)
                queue.Enqueue(current.Right);
            }

            Console.WriteLine();
        }
        /// <summary>
        /// Find the Lowest Common Ancester 
        /// </summary>
        /// <param name="btNode">Binary Tree</param>
        /// <param name="p">BinaryTreeNode Node to found common parent with <para>q</para></param>
        /// <param name="q">BinaryTreeNode Node to found common parent with <para>p</para></param>
        internal BinaryTreeNode LowestCommonAncestor(BinaryTreeNode btNode, BinaryTreeNode p, BinaryTreeNode q)
        {

            if (btNode == null)
                return null;
            if ((btNode == p || btNode == q))
            {
                Console.WriteLine("p or q is the root.  Root: {0} - p: {1} - q: {2}", btNode.Value, p.Value, q.Value);
                return btNode;
            }
            else
            {
                Console.WriteLine("Getting the LCA of p and q in left subtree. Current node: {0}", btNode.Value);                
                BinaryTreeNode left = LowestCommonAncestor(btNode.Left, p, q);
                Console.WriteLine("Getting the LCA of p and q in right subtree. Current node: {0}", btNode.Value);
                BinaryTreeNode right = LowestCommonAncestor(btNode.Right, p, q);

                
                if (left != null && right != null)
                {
                    Console.WriteLine("If p ({0}) or q ({1})is in leftsubtree and other is in right", p.Value, q.Value);
                    Console.WriteLine("then then root ({0}) it the LCA", btNode.Value);
                    return btNode;
                }
                else if (left != null)
                {
                    Console.WriteLine("else if left ({0}) is not null, left is LCA", left.Value);
                    return left;
                }
                else if (right != null)
                {
                    Console.WriteLine("else right ({0}) is LCA", right.Value);
                    return right;
                }
                else
                {
                    return null;
                }
            }           
        }

        internal bool IsBalanced(BinaryTreeNode btNode)
        {
            int left = GetLevels(btNode.Left);
            int rigth = GetLevels(btNode.Right);

            if (Math.Abs(left - rigth) > 1)
                return false;
            else
                return true;
        }
        private int GetLevels(BinaryTreeNode node)
        {
            if (node == null)
                return 0;

            int left = GetLevels(node.Left) + 1;
            int right = GetLevels(node.Right) + 1;

            return left < right ? right : left;

        }

        internal bool IsBinarySearchTree(BinaryTreeNode btNode)
        {
            if (btNode != null)
            {
                if (btNode.Left != null && btNode.Value < btNode.Left.Value)
                    return false;
                IsBinarySearchTree(btNode.Left);

                if (btNode.Right != null && btNode.Value >= btNode.Right.Value)
                    return false;
                IsBinarySearchTree(btNode.Right);
            }

            return true;
        }
        #endregion
    }

    public  class BinaryTreeNode
    {
        public int Value { get; set; }
        public BinaryTreeNode Left { get; set; }
        public BinaryTreeNode Right { get; set; }
        
        public BinaryTreeNode(int value)           
        {
            this.Left = null;
            this.Right = null;
            Value = value;
        }

        public void DisplayNode()
        {
            if (this != null)
                Console.Write(" {0} ", this.Value);
        }
    }
}
